---
id: unit5
title: 第五章
---

### 数组旋转 k 步

```js
// 旋转数组k 步一使用 pop 和unshift
function rotate1(arr, k) {
  const length = arr.length;
  if (!k || length === 0) return arr;

  const step = Math.abs(k % length);

  // o^2
  for (let i = 0; i < step; i++) {
    const n = arr.pop();
    if (n) arr.unshift(n); // 数组是一个有序结构，unshift 操作非常慢！ ！! o(n)
  }

  return arr;
}

let arr = rotate1([1, 3, 4, 5], 2);
console.log(arr); // [4,5,1,3]

// 时间复杂度 o（n^2） ，空间复杂度 0(1)
```

```js
// 旋转数组k 步一使用 slice concat
function rotate2(arr, k) {
  const length = arr.length;
  if (!k || length === 0) return arr;
  const step = Math.abs(k % length);

  const part1 = arr.slice(-step);
  const part2 = arr.slice(0, length - step);
  const part3 = part1.concat(part2);
  return part3;
}

let arr = rotate2([1, 3, 4, 5], 2);
console.log(arr); // [4,5,1,3]

// 时间复杂度o(1），空间复杂度o(n)
```

- 性能测试

```js
console.time("rotate1");
rotate1(arr1, 90000);
console.timeEnd("rotate1"); // rotate1: 1041.655029296875 ms

console.time("rotate2");
rotate2(arr2, 90000);
console.timeEnd("rotate2"); // rotate2: 2.491943359375 ms
```

比复杂度更重要的是：代码逻辑清晰，易读

### 判断字符串是否括号匹配

一个字符串 s 可能包含{}（）[]三种括号;
如(a{b}c)匹配，而(a(b 或(a(b}c) 就不匹配,判断是否匹配的,

- 思路
  - 遇到左括号{（[就压栈
  - 遇到右括号}）]就判断栈顶，匹配则出栈
  - 最后判断 length 是否为 0

```js
function isMatch(left, right) {
  if (left === "{" && right === "}") return true;
  if (left === "[" && right === "]") return true;
  if (left === "(" && right === ")") return true;

  return false;
}

function matchBrack(str) {
  let length = str.length;
  if (length === 0) return true;

  let stack = [];
  const leftSymbol = "{[(";
  const rightSymbol = ")]}";
  for (let k = 0; k < length; k++) {
    const s = str[k];

    if (leftSymbol.includes(s)) {
      stack.push(s); //压入
    } else if (rightSymbol.includes(s)) {
      // 右括号，判断栈顶（是否出栈）
      const top = stack[stack.length - 1];
      if (isMatch(top, s)) {
        stack.pop();
      } else {
        return false;
      }
    }
  }

  return stack.length === 0;
}

let abc = matchBrack("[1{2}3]");
```

### 两个栈实现一个队列

功能要求有：add delete length

```js
class MyQueue {
  stack1 = [];
  stack2 = [];
  add(n) {
    this.stack1.push(n);
  }
  delete() {
    let res;
    const stack1 = this.stack1;
    const stack2 = this.stack2;

    while (stack1.length) {
      const n = stack1.pop();
      if (n != null) stack2.push(n);
    }

    res = stack2.pop();
    while (stack2.length) {
      const n = stack2.pop();
      if (n != null) stack1.push(n);
    }

    return res || null;
  }

  get length() {
    return this.stack1.length;
  }
}

const q = new MyQueue();
q.add(1);
q.add(2);
q.add(3);
console.info(q.stack1);
console.info(q.length);
console.info(q.delete());
console.info(q.stack1);
```

- 时间复杂度：add O(1); delete O(n)
- 空间复杂度，整体是 O(n)

### 链表

链表是一种物理结构（非逻辑结构） ，类似于数组
数组需要一段连续的内存区间，而链表是零散的
链表节点的数据结构 { value, next?, prev?}

```js
function createLinkList() {
  const length = arr.length;
  if (length === 0) throw new Error("arr is empty");
}
```

- 根据数组创建链表

### 用 JS 实现二分查找，并说明时间复杂度

- 思路
  - 递归 - 代码逻辑更加清晰
  - 非递归 - 性能更好
  - 时间复杂度 o(logn)-非常快

```js
// while
function binarySearch1(arr, target) {
  const length = arr.length;
  if (length === 0) return -1;

  let startIndex = 0;
  let endIndex = length - 1;

  while (startIndex <= endIndex) {
    const midIndex = Math.floor((startIndex + endIndex) / 2);
    const midValue = arr[midIndex];

    if (target < midValue) {
      // 目标值较小，则继续在左侧查找
      endIndex = midIndex - 1;
    } else if (target > midValue) {
      // 目标值较大，则继续在右侧查找
      startIndex = midIndex + 1;
    } else {
      // 相等返回
      return midIndex;
    }
  }

  return -1;
}

const arr = [10, 20, 30, 40, 50, 60];
const target = 40;
console.log(binarySearch1(arr, target));

// 递归
function binarySearch2(arr, target, startIndex, endIndex) {
  const length = arr.length;
  if (length === 0) return -1;

  // 开始和结束的范围

  if (startIndex == null) startIndex = 0;
  if (endIndex == null) endIndex = length - 1;

  // 如果start 和end 相遇，则结束
  if (startIndex > endIndex) return -1;

  // 中间位置
  const midIndex = Math.floor((startIndex + endIndex) / 2);
  const midValue = arr[midIndex];

  if (target < midValue) {
    // 目标值较小，则继续在左侧查找
    return binarySearch2(arr, target, startIndex, midIndex - 1);
  } else if (target > midValue) {
    // 目标值较大，则继续在右侧查找
    return binarySearch2(arr, target, midIndex + 1, endIndex);
  } else {
    // 相等返回
    return midIndex;
  }
}

const arr2 = [10, 20, 30, 40, 50, 60];
const target2 = 40;
console.log(binarySearch2(arr2, target2));

// 性能测试
// 性能测试
console.time("search1");
for (let k = 0; k < 30000; k++) {
  binarySearch1(arr, target);
}
console.timeEnd("search1"); // search1: 6.93408203125 ms

console.time("search2");
for (let k = 0; k < 30000; k++) {
  binarySearch2(arr, target);
}
console.timeEnd("search2"); // search2: 18.10791015625 ms

console.time("search3");
for (let k = 0; k < 30000; k++) {
  arr.includes(target);
}
console.timeEnd("search3");

console.time("search4");
for (let k = 0; k < 30000; k++) {
  arr.findIndex((item) => item === target);
}
console.timeEnd("search4");
```
- •凡有序，必二分
- 凡二分，时间复杂度必包含 Ollogn)！！！


### 给一个数组，找出其中和为 n 的两个元素
- 有一个递增的数组[1,2,4,7.11, 15] 和
- 数组中有两个数，和是n。即4+ 11=== 15

- 常规思路
    - 嵌套循环，找到一个数，然后去遍历下一个数，求和，判断
    - 时间复杂度是 O（n^2），不可用

